1. Field of the Invention
The present invention relates to a Reed-Solomon decoder, and more particularly, to a memory device for use in a high-speed pipelined Reed-Solomon decoder, a method of accessing the memory device, and a Reed-Solomon decoder having the memory device.
2. Description of the Related Art
With advancement in digital signal processing techniques, a variety of techniques for dealing with errors in data in a channel or media, i.e., restoring the original state of data, have been developed. Among the variety of error correction techniques, the Reed-Solomon (RS) code, which is a kind of linear block code, has been extensively used. In general, a RS encoder adds parity symbols of 2 t to k data symbols to form a code word including n-bits, e.g., 8-bit symbols.
Here, 2 t will now be expressed to be the same as n-k, and the RS code word is specified as RS(n,k). The RS code has been widely used because of the great error correction capability of an RS decoder and its efficient encoding/decoding procedures.
A decoding procedure performed by the RS decoder is more complicated than an encoding procedure. Also, an increase in systems requiring high-speed digital data processing has resulted in a need for hardware capable of decoding data through high-speed digital processing.
In general, the RS decoder includes five or four-stage processing blocks: five stages for both error and erasure corrections, and four stages for only error correction. As for the five-stage RS decoder for both error and erasure corrections, decoding is carried out by the following procedures: (i) a first-stage processing block s1 generates a syndrome from input data, and counts and buffers erasure flags applied in synchronization with the input data; (ii) a second-stage processing block s2 modifies the syndrome in response to the buffered erasure flags and generates an erasure locator polynomial; (iii) a third-stage processing block s3 calculates the coefficients for the error locator polynomial and an error evaluator polynomial, using the modified syndrome and the erasure locator polynomial. Here, a predetermined algorithm, such as the Euclid algorithm, may be applied to find the coefficients of the polynomials; (iv) a fourth-stage processing block s4 calculates actual error locations and error values from the error locator and error evaluator polynomials with the coefficients, using the Chien Search algorithm; and (v) a fifth-stage processing block s5 corrects the errors of the input data according to the known error locations and error values. Meanwhile, as for a RS decoder for only error corrections, the second-stage processing block s2 is not required, and therefore, decoding is performed only by four-stage procedures.
During the RS decoding process, memory access is required in the first and fifth stages (first and fourth stages for only error correction). That is, the input data are written to a memory in the first stage, and the data stored in the memory is read to correct errors in the fifth stage. Thus, each stage of the decoding can be influenced by time required to access the memory.
A growing need for high-speed processing systems has resulted in development of a pipelined RS decoder in which processing blocks for the respective stages are arranged in a pipeline structure. However, in the case of the pipelined RS decoder, a processing stage having the longest latency in the decoding process contributes as the bottleneck stage in processing one frame of data. Thus, each stage of the decoding can be influenced by time required to access the memory. Given that the length of one frame of data is n, the maximum latency for each stage can be defined within n cycles. However, when decoding one frame of data, 2n or more cycles are required for accessing the memory in the first and fifth stages. In consequence, the memory access time is two or more times longer than the latency for each stage, so that the operating speed of the entire circuit decreases.
To solve this problem, approaches have been made to increase the rate of a system clock signal for the operation of each stage two times or more as fast as the rate of a data input clock signal used to write data in a memory. However, an increase in the system clock signal rate consumes a large amount of power. Also, if a data input clock signal rate is fast, the system clock signal rate cannot be increased over a predetermined rate. The operation speed of the RS decoder is limited by the memory access time.